This invention relates to methods and apparatus for decoding data, and to communications systems incorporating such methods and apparatus; in particular, though not exclusively, the invention relates to such methods, apparatus and systems for decoding data transmitted using multi-carrier frequency division multiplexing, such as coded orthogonal frequency division multiplexing (COFDM).
The increasingly widespread use of powerful computer-based equipment and appliances is resulting in rapidly increasing requirements for high-speed, high-capacity communications, based on both wireline and wireless techniques. One way of accommodating this increase is to design communications systems for operation at higher and higher symbol rates. However, an increase in symbol rate typically involves a corresponding decrease in inter-symbol spacing, and this in turn can lead to greater inter-symbol interference (ISI) and consequential errors in symbols as received. In the case of wireline links ISI can arise, for example, from signal reflections at imperfectly matched interfaces between different portions of the communications link. For wireless links a significant source of ISI is multi-path propagation involving signal reflections from objects (such as buildings) in the space traversed by the signals; mobile wireless communications can be especially susceptible to ISI from this source, because movement of a mobile unit using the link can cause continuous and complex variation in the multiple propagation paths extending to the mobile unit.
A technique which is being actively studied and developed to increase communications system capacity and counteract ISI is multi-carrier (or multitone) frequency division multiplex operation, such as COFDM operation. In a COFDM system multiple symbols are transmitted simultaneously, each symbol controlling the modulation (e.g. by phase-shift keying) of a respective one of multiple carrier signals having closely-spaced frequencies. By choosing the carrier-frequency spacing to have an appropriate relationship to the rate at which symbols are transmitted on each carrier, it is possible to ensure that each individual carrier can be demodulated without interference from the carriers adjacent to it (in which case the carriers are said to be orthogonal to one another). The set of symbols transmitted simultaneously on respective carriers during a symbol period (a code word) is chosen to encode a group of data symbols (a data word) and includes redundancy (i.e. the code word has more symbols than the data word); this redundancy is used upon reception for detection of errors in the symbols as received, and, if desired, for correction of those errors.
COFDM systems counteract ISI in part because the transmission of multiple symbols in parallel enables a desired data rate to be attained with a lower symbol rate than would be necessary if a serial system were used to transmit individual symbols in succession. A lower symbol rate implies a longer duration for each symbol and thus a longer period between symbol transitions, which reduces the impact of ISI. The error detection/correction capabilities provided by the inclusion of redundancy enhance the resistance to data corruption, by enabling some errors which occur in received symbols owing to signal fading and other causes to be detected or corrected.
However, present COFDM systems encounter difficulties in obtaining the maximum potential benefit for a particular transmitted signal power, owing to limitations arising from the typical peak-to-mean envelope power ratio (PMEPR) of the complex-valued signal from which the actual transmitted signal is derived. Because this transmitted signal is effectively the sum of several signals at closely spaced frequencies and with respective phases which change at each symbol transition, the overall signal tends to exhibit transient pronounced peaks separated by substantially longer intervals of much lower though still varying amplitude. The transmitting equipment must be adjusted to reproduce the peaks without clipping or other distortion, so for much of the time, in the intervals between peaks, that equipment is operating at a signal level well below its maximum capability. As a result the geographical range of the equipment is significantly lower than would be expected for its nominal power rating, or alternatively a much more powerful equipment must be provided to cover the desired range and then operated inefficiently.
It is known that this problem can in principle be alleviated by careful selection of the code words which encode the possible data words (for example in xe2x80x98Block coding scheme for reduction of peak to mean envelope power ratio of multicarrier transmission schemesxe2x80x99 by A. E. Jones, T. A. Wilkinson and S. K. Barton, Electronics Letters, Dec. 8, 1994, vol.30, no.25, pp. 2098-2099). However, in selecting code words to reduce the PMEPR it is important also to ensure the code has good error correction properties. Furthermore, implementation of a high-throughput communications system desirably involves the use of long code words and of rapid encoding and decoding procedures; the use of simple look-up tables, though readily implemented, does not lend itself to rapid operation using compact (and low-power, inexpensive) circuitry, especially during decoding, if the number of valid code words to be checked is large, as is typically the case with long code words (e.g. more than about 16 symbols). It is therefore preferable for encoding and decoding operations to be definable in terms of some analytical procedure which for example performs combinatorial logic on the data word or code word symbols to convert one to the other, or at least restricts the size of any look-up table which is used.
An additional difficulty is presented by the sheer quantity of possible code words from which a selection may be made to define a code for use in a typical system. As the number of symbols in a code word increases the number of possible code words increases much faster, even for binary symbols; for symbols having just three (ternary) or four (quaternary) possible values, the number of possible codes available becomes so huge even for quite short code words that a simple exhaustive search through all possible code words is not feasible in a realistic time even just to minimize the PMEPR. Attempting to satisfy error correction and implementational requirements as well merely adds to the difficulty of such a search, especially as it will not even be known whether there actually exists a code word set which is of the desired size and which simultaneously satisfies preferred criteria relating to PMEPR, error detection/correction and ease of encoding and decoding. This difficulty is further exacerbated by the desirability of having a large number of code words available for use in the chosen code, in order to be able to encode a large number of different data words (i.e. data words containing relatively many symbols) and thus attain an acceptably high data transfer rate.
It is known that certain kinds of codes may have some desirable properties. Thus the paper xe2x80x98Synthesis of Power Efficient Multitone Signals with Flat Amplitude Spectrumxe2x80x99 by B. M. Popovixc4x87, IEEE Transactions on Communications, vol.39, no.7, July 1991, pp.1031-1033 indicates that any binary or polyphase complementary sequence can be used to construct a multitone signal such that the crest factor of the real-valued signal is less than or equal to 6 dBV (which corresponds to the PMEPR of the complex-valued signal being less than or equal to 3 dB). Examples of these sequences have been described, as in the case of binary Golay complementary sequence pairs (xe2x80x98Complementary seriesxe2x80x99 by M. J. E. Golay, IRE Transactions on Information Theory, vol.IT-7, April 1961, pp. 82-87). However, Popovixc4x87""s paper is directed to situations such as multipath fading measurements and multitone jamming, in which a single code word can be used continuously in generating the required signal. Accordingly Popovixc4x87 gives no guidance on how multiple such sequences could be identified just to attain the 3 dB limit on PMEPR in a practical code for conveying information; and no mention whatsoever is made of the other requirements mentioned above for a code suitable for practical implementation. Indeed Popovixc4x87 states that xe2x80x9cthe construction of multitone signals having minimum peak-to-peak amplitude is an old problem that still has no analytical solutionxe2x80x9d.
It should be noted that Golay complementary sequence pairs and codes defined using them are different from and should not be confused with so-called Golay codes; Golay complementary sequence pairs and Golay codes were first defined, independently of one another, by the same researcher and for that reason alone both are referred to by his name.
Methods and apparatus for encoding and decoding are described in International patent application no. PCT/GB 97/02 464 (WO 98/11 698), in which a substantial number of different code words are identifiable in practice, despite the potentially huge search space of possible code words, and which provide a predictable low limit on PMEPR, have specified error detection/correction properties and are feasible for implementation in high-speed circuitry. In particular codes are described for systems in which each transmitted symbol has 2j different possible values where j is a positive integer, such as binary (j=1), quaternary (j=2), octary (j=3), and higher orders. Techniques are also described for decoding these codes, involving use of the fast Hadamard transform (FHT). These techniques are effective, but they nonetheless entail substantial amounts of processing, and many applications of the fast Hadamard transform, especially in the case of octary and higher-order codes and longer code words (i.e. with more symbols).
It is an object of this invention to provide methods and apparatus for decoding such codes and which provide a reduction in the amount of processing required.
According to one aspect of this invention there is provided a method of identifying a code word within a predetermined set of code words, the code words containing symbols each having pj different possible values where p is a prime and j is an integer greater than 1, wherein
a plurality of constituents, constituent1 to constituentk, of said code word, each constituent identifying an element of a predetermined subset of a predetermined linear code, are derived in respect of an input word; and
said k constituents are combined to identify said code word according to a relationship
(pb(k)*constituentk+pb(kxe2x88x921)*constituentkxe2x88x921+ . . . +pb(2)*constituent2+pb(1)*constituent1)mod pj
where each b(x) is an integer, j greater than b(k) greater than b(kxe2x88x921) greater than  . . .  greater than b(2) greater than b(1)xe2x89xa70, * indicates symbol-wise multiplication, + indicates symbol-wise addition and mod indicates symbol-wise modular reduction.
According to another aspect of this invention there is provided a method of identifying a code word within a predetermined set of code words, the code words containing symbols each having 2j different possible values where j is an integer greater than 1, comprising the steps of
receiving an input word;
deriving the result of reducing the input word modulo 21;
deriving a first constituent, constituent1, by applying a Hadamard transform operation, or equivalent thereof, in respect of the result of said reduction modulo 21;
setting a modifier equal to constituent1;
for each successive value of a counter x from 2 to j:
deriving the result of symbol-wise subtraction of the current value of the modifier from the input word modulo 2x;
deriving another constituent, constituentx, by applying a Hadamard transform operation, or equivalent thereof, in respect of the result of said subtraction modulo 2x;
setting the modifier equal to the symbol-wise sum modulo 2j of the modifier and the product of 2xxe2x88x921 times constituentx;
and identifying the code word as having the final value of said modifier.
According to a further aspect of this invention there is provided apparatus for identifying a code word within a predetermined set of code words, the code words containing symbols each having pj different possible values where p is a prime and j is an integer greater than 1, comprising:
a decoder for deriving in respect of an input word a plurality of constituents, constituent1 to constituentk, of said code word, each constituent identifying an element of a predetermined subset of a predetermined linear code; and
a combiner for combining said k constituents to identify said code word according to a relationship
(pb(k)*constituentk+pb(kxe2x88x921)*constituentkxe2x88x921+ . . . +pb(2)*constituent2+pb(1)*constituent1)mod pj
where each b(x) is an integer, j greater than b(k) greater than b(kxe2x88x921) greater than  . . .  greater than b(2) greater than b(1)xe2x89xa70, * indicates symbol-wise multiplication, + indicates symbol-wise addition and mod indicates symbol-wise modular reduction.
Decoders implementing this invention enable decoding to be accomplished with relatively few applications of the fast Hadamard transform. For example, a quaternary code word can be decoded with just two successive applications of the FHT, and an octary code word with just three, irrespective of the length of the code word.